package com.warren.test;

/**
 * @version V1.0
 * @Description:
 * @author: warren
 * @date: 2022/7/8$ 16:17$
 */

public class ShortestPath {

    public static void main(String[] args) {
        int[][] arr = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
        System.out.println("路径：");
        System.out.println("最小值为：" + getMinPath(arr));
    }

    private static int getMinPath(int[][] arr) {
        if (arr == null || arr.length == 0) {
            return 0;
        }
        int row = arr.length;
        int col = arr[0].length;
        //用来保存计算的中间值
        int[][] cache = new int[row][col];
        cache[0][0] = arr[0][0];
        for (int i = 1; i < col; i++) {
            cache[0][i] = cache[0][i - 1] + arr[0][i];
        }
        for (int j = 1; j < row; j++) {
            cache[j][0] = cache[j - 1][0] + arr[j][0];
        }
        //在遍历二维数组的过程中不断把计算结果保存到cache中
        for (int i = 1; i < row; i++) {
            for (int j = 1; j < col; j++) {
                //可以确定选择的路线为a[i][j-1]
                if (cache[i - 1][j] > cache[i][j - 1]) {
                    cache[i][j] = cache[i][j - 1] + arr[i][j];
                    System.out.println("[" + i + "," + (j - 1) + "] ");
                    //可以确定选择的路线为arr[i-1][j]
                } else {
                    cache[i][j] = cache[i - 1][j] + arr[i][j];
                    System.out.println("[" + (i - 1) + "," + j + "] ");
                }
            }
        }
        System.out.println("[" + (row - 1) + "," + (col - 1) + "]");
        return cache[row - 1][col - 1];
    }
}
